//
//  Problem1636.swift
//  TestProject
//
//  Created by 武侠 on 2021/4/16.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1636. 按照频率将数组升序排序
 给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。

 请你返回排序后的数组。


 示例 1：
     输入：nums = [1,1,2,2,2,3]
     输出：[3,1,1,2,2,2]
     解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
 示例 2：
     输入：nums = [2,3,1,3,2]
     输出：[1,3,3,2,2]
     解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。
 示例 3：
     输入：nums = [-1,1,-6,4,5,-6,1,4,1]
     输出：[5,-1,4,4,-6,-6,1,1,1]
 提示：
     1 <= nums.length <= 100
     -100 <= nums[i] <= 100
 */
@objcMembers class Problem1636: NSObject {
    func solution() {
        print(frequencySortClear([1,1,2,2,2,3]))
        print(frequencySortClear([2,3,1,3,2]))
        print(frequencySortClear([-1,1,-6,4,5,-6,1,4,1]))
    }
    
    /*
     暴力方法
     1: 创建一个字典dic:求出所有数组的个数
     2: 将字典的values：按照排序，然后拼接
     */
    func frequencySort(_ nums: [Int]) -> [Int] {
        var dic:[Int: [Int]] = [:]
        for num in nums {
            dic[num, default: []].append(num)
        }
        
        let list = dic.values.sorted { (first, second) -> Bool in
            if first.count == second.count {
                return first[0] > second[0]
            } else {
                return first.count < second.count
            }
        }
        
        return list.reduce([]) { (result, next) -> [Int] in
            return result + next
        }
    }
    
    /*
     1: 将相同个数的元素变成：次数+元素，例如数组中有3个2：3002，然后排序，这样可以根据次数进行排序
     2: 因为个数相同时，降序排序，例如 有3个2 3个5: 3002和3005，2还是排在5前面， 所以得变形 次数+100-元素
     （为什么让100减去呢？ 因为：-100 <= nums[i] <= 100）这样就变成：
     3098 3095 这样2就排在前面
     */
    func frequencySortClear(_ nums: [Int]) -> [Int] {
        // 统计每个元素的次数
        var nlist = Array(repeating: 0, count: 201)
        for n in nums {
            nlist[n + 100] += 1
        }
        
        var list = nums
        // 将元素变形
        for (i,n) in list.enumerated() {
            // 次数 + 100 - 元素
            list[i] = nlist[n+100] * 1000 + 100 - n
        }
        
        // 排序：个数不同：升序，相同：降序
        list.sort()
        
        // 变回去
        return list.map { (n) -> Int in
            return 100 - n % 1000
        }
    }
}
